package com.ljx.QueueStack;

/**
 * @author 李加喜
 * @Package com.ljx.QueueStack
 * @date 2021-12-10 9:46
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 239 滑动窗口的最大值
 */
public class WindowDeQueue {
    public static void main(String[] args) {

    }
    //定义单调队列

    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue window = new MonotonicQueue();
        List<Integer> res = new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            if (i<k-1){
                //现将窗口填满前k-1个值
                window.push(nums[i]);
            }else {
                //窗口向前滑动  添加新的数字
                window.push(nums[i]);
                res.add(window.max());
                //如果队首存在的话  就会将队首元素进行删除掉
                //之所以要判断 data.front() == n，是因为我们想删除的队头元素 n 可能已经被「压扁」了，可能已经不
                //存在了，所以这时候就不⽤删除了
                window.pop(nums[i-k+1]);

            }
        }
        // 转换为int[]
        int[] arr=new int[res.size()];
        for (int i=0;i<res.size();i++){
            arr[i]=res.get(i);
        }
        return arr;
    }
}

class MonotonicQueue {
    LinkedList<Integer> q = new LinkedList<>();

    public void push(int n) {
        // 将小于n的元素全部删除  向前挤压  q.getLast()获取队尾的元素
        while (!q.isEmpty() && q.getLast() < n) {
            q.pollLast();
        }
        //将n加入到尾部
        q.addLast(n);
    }

    //这个时候的队首一定是最大的值
    public int max() {
        return q.getFirst();
    }

    //如果当前值等于队首的值  那么也将队首的值进行删除
    public void pop(int n) {
        if (n == q.getFirst()) {
            q.pollFirst();
        }
    }
}